#!/usr/bin/env python3.4

from math import sqrt
from time import time
from struct import pack
from struct import unpack

def inv_sqrt(number):
	x = number * 0.5
	y = number
	i = unpack("I", pack("f", y))[0]
	i = 0x5f3759df - (i>>1)
	y = unpack("f", pack("I", i))[0]
	y = y * (1.5 - (x * y * y))
	y = y * (1.5  - (x * y * y))
	return number * y

def Fb1Q(n):
	C = 2.23606797749979 #sqrt(5)
	A = (1 + C) / 2
	B = (1 - C) / 2
	for x in range(1, n+1):
		yield int((A**x - B**x) / C)

def Fb1(n):
	C = 2.23606797749979 #sqrt(5)
	A = (1 + C) / 2
	B = (1 - C) / 2
	return int((A**n - B**n) / C)

def Fb2Q(n):
	curr = prev = 1
	for x in range(1, n+1):
		if x == 1 or x == 2: yield 1
		else:
			curr, prev = curr +  prev, curr
			yield int(curr)

def Fb2(n):
	curr = prev = 1
	for x in range(1, n+1):
		if x == 1 or x == 2:
			continue
		else:
			curr, prev = curr +  prev, curr
	return curr

if __name__ == '__main__':
	n = 20
	start = time()
	res = [x for x in Fb1Q(n)]
	end = time()
	print(res, "\nrunning time of Fb1Q(%d) is %f\n" % (n, end - start))
	#print("running time of Fb1Q(%d) is %f" % (n, end - start))

	start = time()
	res = [x for x in Fb2Q(n)]
	end = time()
	print(res, "\nrunning time of Fb2Q(%d) is %f\n" % (n, end - start))
	#print("running time of Fb2Q(%d) is %f" % (n, end - start))

	start = time()
	res = [Fb1(x) for x in range(1, n+1)]
	end = time()
	print(res, "\nrunning time of Fb1(%d) is %f\n" % (n, end - start))

	start = time()
	res = [Fb2(x) for x in range(1, n+1)]
	end = time()
	print(res, "\nrunning time of Fb2(%d) is %f\n" % (n, end - start))

#	print("math sqrt(5) is %f" % sqrt(5))
#	print("my sqrt(5) is %f" % inv_sqrt(5))
